#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <cmath>
class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		
		int i,j;
		//move non-positives to right
		for(i=-1,j=0;j<n;j++)
		{
			if(A[j]>0)
			{
				i++;
				int tmp = A[i];
				A[i] = A[j];
				A[j] = tmp;
			}
		}

		if(i<0)
			return 1;

		for(int k=0;k<=i;k++)
		{
			if(abs(A[k])<=(i+1))
			{
				A[abs(A[k])-1] = -1*abs(A[abs(A[k])-1]);
			}
		}

		for(int k=0;k<=i;k++)
		{
			if(A[k] > 0)
				return k+1;
		}

		return i+2;
        
    }
};
#endif